package com.javabase.y2022.m04.day0428.v01;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/4/28 下午 07:10
 * @version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().climbStairs(45));
    }

    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = -1;
        }
        return dp(n, dp);
    }

    public int dp(int i, int[] dp) {
        if (dp[i] != -1) {
            return dp[i];
        }
        if (i == 1) {
            dp[1] = 1;
            return 1;
        } else if (i == 2) {
            dp[2] = 2;
            return 2;
        }
        dp[i] = dp(i - 1, dp) + dp(i - 2, dp);
        return dp[i];
    }
}
